#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//For test purpose
#define B_VALUE 15	//Knapsack maximum value
#define N_VALUE 5	//Number of objects
#define K_VALUE 15	//K-solutions


//int main(char* args, int argc){
//
//	//Begin initialization
//	int a[] = { 3 , 4 , 5 , 6 , 7};
//	int c[] = { 4 , 3 , 5 , 7 , 8};
//	int r,s,j,t,m,i, z = 0, offset = 0;
//
//	int colums = N_VALUE; //columns number
//	
//	//Computational time measuring variables
//	clock_t begin, end;
//	double time_spent;
//
//	//Memory allocation
//	int*matrix = (int*) malloc(sizeof(int)*(B_VALUE+1)*N_VALUE);
//
//	//We will simulate the matrix in this way
//	//int offset = i * colums (columns number) + j;
//	//now mat[offset] corresponds to m(i, j)
//	//For memory efficient use (locality principle)
//
//	for(r=0; r <= B_VALUE; r++){
//		for(s=0; s < N_VALUE; s++){
//			offset = r * colums + s;
//			if(r==0)
//				matrix[offset] = 0;
//			else
//				matrix[offset] = -1;
//		}
//	}
//
//	//Begin Forward Enumeration
//	begin = clock();
//	//Begin Initial ramification
//	for(j=0; j < N_VALUE; j++){
//		offset = a[j] * N_VALUE + j;
//		matrix[offset] = c[j];
//	}
//	//End Initial ramification
//
//	//Begin Ramification of supernodes
//	for(t=a[0]; t <= B_VALUE - a[0]; t++){
//		m = N_VALUE;
//		
//		for(i=0; i < N_VALUE; i++){
//			offset = t * colums + i;
//			if(matrix[offset] >= 0){
//				m = i;
//				break;
//			}
//		}
//
//		if(m != N_VALUE){
//			offset = t * colums + m;
//			z = matrix[offset];
//			for(i=m; i < N_VALUE; i++){
//				if(t+a[i] <= B_VALUE){
//					offset = t * colums + i;
//					if(matrix[offset] > z)
//						z = matrix[offset];
//					offset = (t+a[i]) * colums + i;
//					matrix[offset] = z + c[i];
//				}
//			}
//		}
//	}
//	//End Ramification of supernodes
//	end = clock();
//	time_spent = (double) (end-begin);
//	//End Forward Enumeration
//
//	//Print the resulted matrix
//	for(r=0; r <= B_VALUE; r++){
//		for(s=0; s < N_VALUE; s++){
//			offset = r * colums + s;
//			printf("%i\t", matrix[offset]);
//		}
//		printf("\n");
//	}
//	//Print computational time
//	printf("Computational time: %f\n", time_spent);
//
//
//	free(matrix);
//
//	return 0;
//}
